home *** CD-ROM | disk | FTP | other *** search
/ NeXT Education Software Sampler 1992 Fall / NeXT Education Software Sampler 1992 Fall.iso / Programming / Source / plot3d / Expression.m < prev    next >
Encoding:
Text File  |  1992-08-16  |  22.7 KB  |  785 lines
  1.  
  2. /*
  3.     Expression.m
  4.  
  5.     The Expression class is implemented using a grammar generated by the Unix
  6.     program yacc, and a lexical scanner generated by the Unix program lex.
  7.     The only interface between these parsing modules and this class is the
  8.     function _EXPParseExpression, which actually performs the parse.  The
  9.     results of the parse are returned in two data structures: a parse tree
  10.     representing the expression and a hashtable which holds that variables
  11.     found in the expression.
  12.  
  13.     The parse tree's nodes are Term structs (declared in exprDefs.h).  There
  14.     is a node for each piece of the expression.  For example, when the
  15.     expression "A+5" is parsed, three nodes result.  The top node of the tree
  16.     represents the binary operator "+".  This top node has two subnodes.  The
  17.     first subnode represents the variable "A".  The second represents the
  18.     integer constant "5".  Since variables can appear more than once in an
  19.     expression, their nodes may occur more than once in the parse tree.
  20.     
  21.     A parse tree is evaluated by doing a depth first traversal of the tree,
  22.     bubbling up the results of each sub-tree until the final value rises
  23.     to the top.
  24. */
  25.  
  26.  
  27. #import "Expression.h"
  28. #import "exprDefs.h"
  29. #import <stdlib.h>
  30. #import <math.h>
  31. #import <appkit/nextstd.h>
  32. #import <string.h>
  33.  
  34. /* declaration of methods static to this class */
  35. @interface Expression(ExpressionPrivate)
  36. - (void)_updateResults;
  37. - (EXPTermPtr)_addVarTerm:(const char *)name;
  38. @end
  39.  
  40. @implementation Expression
  41.  
  42. /* function which can be applied to parse tree nodes with applyToTerms() */
  43. typedef void ParseTreeFunc(void *info, Term *term);
  44.  
  45. static void freeContents(Expression *self);
  46. static void applyToTerms(Term *t, ParseTreeFunc *func, void *data, int mask);
  47. static void updateTerm(void *data, Term *t);
  48. static float evalTerm(Term *t, int element);
  49. static Term *termOfVar(Expression *self, const char *varName);
  50. static NXHashTable *makeBuiltInFuncTable(NXZone *zone);
  51. static NXHashTable *getBuiltInFuncs(void);
  52. static Function *addFuncTerm(NXHashTable *table, const char *name, int min, int max, EXPTermEvalFunc *func);
  53. static void safeFree(void **data);
  54. static EXPTermEvalFunc sinStub, cosStub, tanStub;
  55. static EXPTermEvalFunc asinStub, acosStub, atanStub;
  56. static EXPTermEvalFunc expStub, logStub, log10Stub, sqrtStub;
  57. static char *termName(const Term *t);
  58. static void FunctionFree(const void *info, void *data);
  59. static unsigned    VarTermHash(const void *info, const void *data);
  60. static int VarTermCompare(const void *info, const void *data1, const void *data2);
  61.  
  62. /*
  63.  * Shared table of built in functions.  All Expressions which haven't had
  64.  * any application functions added to them shared this table, which contains
  65.  * just the built in functions.
  66.  */
  67. static NXHashTable *BuiltInFuncTable = NULL;
  68.  
  69. /* data for a built in function */
  70. typedef struct _BuiltInFunc {
  71.     const char *name;        /* name of the function */
  72.     EXPTermEvalFunc *func;    /* proc to call for evaluation */
  73. } BuiltInFunc;
  74.  
  75. /* table of built in functions */
  76. static const BuiltInFunc FuncList[] = {
  77.     {"sin", &sinStub},
  78.     {"cos", &cosStub},
  79.     {"tan", &tanStub},
  80.     {"asin", &asinStub},
  81.     {"acos", &acosStub},
  82.     {"atan", &atanStub},
  83.     {"exp", &expStub},
  84.     {"log", &logStub},
  85.     {"log10", &log10Stub},
  86.     {"sqrt", &sqrtStub}
  87. };
  88.  
  89. #define NUM_BUILTIN_FUNCS    (sizeof(FuncList)/sizeof(BuiltInFunc))
  90.  
  91. /* prototype used to create hashtables of variable terms */
  92. static NXHashTablePrototype VarTermProto = {&VarTermHash, &VarTermCompare, (void (*)(const void *info, void *data))&_EXPFreeTerm, 0};
  93.  
  94. - init
  95. {
  96.     [super init];
  97.     resolution = 1;
  98.     varTerms = NXCreateHashTableFromZone(VarTermProto, 0, NULL, [self zone]);
  99.     return self;
  100. }
  101.  
  102. - free
  103. {
  104.     freeContents(self);
  105.   /* if we have a function table and its not the shared one */
  106.     if (validFuncs && validFuncs != BuiltInFuncTable)
  107.     NXFreeHashTable(validFuncs);
  108.     return [super free];
  109. }
  110.  
  111. - (BOOL)parse:(const char *)expressionString
  112. {
  113.     NXZone *zone;
  114.  
  115.     zone = [self zone];
  116.   /* clear away any results from a previous parse */
  117.     freeContents(self);
  118.     varTerms = NXCreateHashTableFromZone(VarTermProto, 0, NULL, zone);
  119.     resultsValid = NO;
  120.     text = NXCopyStringBufferFromZone(expressionString, zone);
  121.     if (!validFuncs)
  122.     validFuncs = getBuiltInFuncs();
  123.     return _EXPParseExpression(text, validFuncs, &parseTree, varTerms, zone);
  124. }
  125.  
  126. - (const char *)text
  127. {
  128.     return text;
  129. }
  130.  
  131. - setResolution:(int)count
  132. {
  133.     if (resolution != count) {
  134.       /*
  135.        * Changing the resolution means we have to recalculate next time
  136.        * we're asked for results
  137.        */
  138.     resultsValid = NO;
  139.     resolution = count;
  140.     }
  141.     return self;
  142. }
  143.  
  144. - (int)resolution
  145. {
  146.     return resolution;
  147. }
  148.  
  149. - setVar:(const char *)varName value:(float)val
  150. {
  151.     Term *t;
  152.  
  153.     resultsValid = NO;        /* must recalc after a var is set */
  154.     t = termOfVar(self, varName);
  155.     if (!t)
  156.     t = [self _addVarTerm:varName];
  157.   /*
  158.    * If the term was previously a vector term, we change it to a variable
  159.    * term (one that has a single value).
  160.    */
  161.     if (t->tag == vectorTerm) {
  162.     t->tag = varTerm;
  163.     safeFree(&(void *)t->data.vector.vals);
  164.     t->data.var.name = t->data.vector.name;
  165.     }
  166.     NX_ASSERT(t->tag == varTerm, "Invalid term type in setVar:value:");
  167.     t->data.var.val = val;
  168.     return self;
  169. }
  170.  
  171. - (float)varValue:(const char *)varName
  172. {
  173.     Term *t;
  174.  
  175.     t = termOfVar(self, varName);
  176.     if (t) {
  177.     if(t->tag == varTerm)
  178.         return t->data.var.val;
  179.     else
  180.         NX_RAISE(expErrInvalidVarType, self, (void *)varName);
  181.     } else
  182.     NX_RAISE(expErrInvalidVarName, self, (void *)varName);
  183. }
  184.  
  185. - setVar:(const char *)varName vector:(float *)vals numVals:(int)count
  186. {
  187.     Term *t;
  188.  
  189.     resultsValid = NO;
  190.     t = termOfVar(self, varName);
  191.     if (!t)
  192.     t = [self _addVarTerm:varName];
  193.   /*
  194.    * If the term was previously a non-vector variable, we change it to a
  195.    * vector variable term.
  196.    */
  197.     if (t->tag == varTerm) {
  198.     t->tag = vectorTerm;
  199.     t->data.vector.name = t->data.var.name;
  200.     t->data.vector.hasRange = NO;
  201.     t->data.vector.vals = NULL;
  202.     t->data.vector.resolution = 0;
  203.     }
  204.     NX_ASSERT(t->tag == vectorTerm, "Invalid term type in setVar:vector:");
  205.     safeFree(&(void *)t->data.vector.vals);
  206.     t->data.vector.resolution = count;
  207.     t->data.vector.vals = vals;
  208.     t->data.vector.changed = YES;
  209.     resolution = count;
  210.     return self;
  211. }
  212.  
  213. - varVector:(const char *)varName vector:(float **)vals numVals:(int *)count;
  214. {
  215.     Term *t;
  216.  
  217.     t = termOfVar(self, varName);
  218.     if (t) {
  219.     if(t->tag == vectorTerm) {
  220.         updateTerm(self, t);
  221.         *count = t->data.vector.resolution;
  222.         *vals = t->data.vector.vals;
  223.     } else
  224.         NX_RAISE(expErrInvalidVarType, self, (void *)varName);
  225.     } else
  226.         NX_RAISE(expErrInvalidVarName, self, (void *)varName);
  227.     return self;
  228. }
  229.  
  230. - setVar:(const char *)varName min:(float)minVal max:(float)maxVal
  231. {
  232.     Term *t;
  233.  
  234.     if (minVal > maxVal)
  235.     NX_RAISE(expErrMinMax, self, NULL);
  236.     resultsValid = NO;
  237.     t = termOfVar(self, varName);
  238.     if (!t)
  239.     t = [self _addVarTerm:varName];
  240.   /*
  241.    * If the term was previously a non-vector variable, we change it to a
  242.    * vector variable term.
  243.    */
  244.     if (t->tag == varTerm) {
  245.     t->tag = vectorTerm;
  246.     t->data.vector.name = t->data.var.name;
  247.     t->data.vector.hasRange = YES;
  248.     t->data.vector.vals = NULL;
  249.     t->data.vector.changed = YES;
  250.     }
  251.     NX_ASSERT(t->tag == vectorTerm, "Invalid term type in setVar:min:max:");
  252.  
  253.   /*
  254.    * We optimize and do nothing if the passed values are the same as our
  255.    * current values.
  256.    */
  257.     if (t->data.vector.changed || t->data.vector.min != minVal || t->data.vector.max != maxVal) {
  258.     safeFree(&(void *)t->data.vector.vals);
  259.     t->data.vector.resolution = 0;
  260.     t->data.vector.min = minVal;
  261.     t->data.vector.max = maxVal;
  262.     t->data.vector.changed = YES;
  263.     }    
  264.     return self;
  265. }
  266.  
  267. - var:(const char *)varName min:(float *)minVal max:(float *)maxVal
  268. {
  269.     Term *t;
  270.  
  271.     t = termOfVar(self, varName);
  272.     if (t) {
  273.     if(t->tag == vectorTerm) {
  274.         updateTerm(self, t);
  275.         *minVal = t->data.vector.min;
  276.         *maxVal = t->data.vector.max;
  277.     } else
  278.         NX_RAISE(expErrInvalidVarType, self, (void *)varName);
  279.     } else
  280.         NX_RAISE(expErrInvalidVarName, self, (void *)varName);
  281.     return self;
  282. }
  283.  
  284. - (float)resultValue
  285. {
  286.     [self _updateResults];
  287.     return *results;
  288. }
  289.  
  290. - resultsVector:(float **)vals numVals:(int *)count
  291. {
  292.     [self _updateResults];
  293.     *vals = results;
  294.     *count = resolution;
  295.     return self;
  296. }
  297.  
  298. - resultsMin:(float *)minVal max:(float *)maxVal
  299. {
  300.     [self _updateResults];
  301.     *minVal = resultsMin;
  302.     *maxVal = resultsMax;
  303.     return self;
  304. }
  305.  
  306. /*
  307.  * Since the varables are all in a NXHashTable, we just use the NXHashTable
  308.  * functions to enumerate through the names of the variables.
  309.  */
  310.  
  311. - (EXPEnumState)beginVariableEnumeration
  312. {
  313.     NXHashState *state;
  314.  
  315.     state = NXZoneMalloc([self zone], sizeof(NXHashState));
  316.     *state = NXInitHashState(varTerms);
  317.     return state;
  318. }
  319.  
  320. - (const char *)nextVariable:(EXPEnumState)state
  321. {
  322.     const Term *t;
  323.  
  324.     if (NXNextHashState(varTerms, (NXHashState *)state, &(void *)t))
  325.     return termName(t);
  326.     else
  327.     return NULL;
  328. }
  329.  
  330. - (void)endVariableEnumeration:(EXPEnumState)state
  331. {
  332.     free(state);
  333. }
  334.  
  335. - addFuncTerm:(const char *)name minArgs:(int)min maxArgs:(int)max
  336.                     evalFunc:(EXPTermEvalFunc *)func
  337. {
  338.     Function *existingType;
  339.  
  340.   /*
  341.    * If we dont have a function table yet, get one.  If we do have one, but
  342.    * its the shared built in table, get a new one that we can safely modify.
  343.    */
  344.     if (!validFuncs || validFuncs == BuiltInFuncTable)
  345.     validFuncs = makeBuiltInFuncTable([self zone]);
  346.     existingType = addFuncTerm(validFuncs, name, min, max, func);
  347.     if (existingType)
  348.     NX_RAISE(expFuncTypeInUse, self, existingType);
  349.     return self;
  350. }
  351.  
  352. - removeFuncTerm:(const char *)name
  353. {
  354.     Function *realFunc;
  355.     Function key;
  356.  
  357.     if (validFuncs) {
  358.       /* look up the func term by name in our table of functions */
  359.     key.name = (char *)name;
  360.     if (realFunc = NXHashGet(validFuncs, &key)) {
  361.       /*
  362.        * If we are using the shared table of built ins, get a new table
  363.        * that we can safely modify (this covers the case of someone
  364.        * wishing to remove a built in function, possibly to redefine it).
  365.        */
  366.         if (validFuncs == BuiltInFuncTable) {
  367.         validFuncs = makeBuiltInFuncTable([self zone]);
  368.         realFunc = NXHashGet(validFuncs, &key);
  369.         }
  370.         NXHashRemove(validFuncs, realFunc);
  371.         free(realFunc);
  372.         return self;
  373.     }
  374.     }
  375.     return self;
  376. }
  377.  
  378. /*
  379.  * This is a utililty routine that recursively applies a function to all
  380.  * terms of a parse tree. data is a blind pointer that is simply passed
  381.  * along through the function call.  The function is only called on terms
  382.  * whose type match the given mask.
  383.  */
  384. static void applyToTerms(Term *t, ParseTreeFunc *func, void *data, int mask)
  385. {
  386.     int i;
  387.     Term **tPtr;
  388.  
  389.     for (i = t->numSubterms, tPtr = t->subterms; i--; tPtr++)
  390.     applyToTerms(*tPtr, func, data, mask);
  391.     if (t->tag & mask)
  392.     (*func)(data, t);
  393. }
  394.  
  395. /*
  396.  * Empties the contents of the Expression.  Since the variable terms can
  397.  * exist multiple times in the tree, we first run through the tree and
  398.  * free all the nodes except that variable nodes.  Then we free the hash
  399.  * table of variable terms, including the terms themselves. 
  400.  */
  401. static void freeContents(Expression *self)
  402. {
  403.     safeFree(&(void *)self->text);
  404.   /* free the non-variable terms */
  405.     if (self->parseTree)
  406.     applyToTerms(self->parseTree, _EXPFreeTerm, NULL, ~(varTerm|vectorTerm));
  407.   /* free the shared variable terms */
  408.     NXFreeHashTable(self->varTerms);
  409.     safeFree(&(void *)self->results);
  410. }
  411.  
  412. /*
  413.  * Allocates a new term of the given type, with room for subterms.  The
  414.  * subterms themselves follow as a variable number of arguments.  The are
  415.  * copied into the subterms list of the new term.
  416.  */
  417. Term *_EXPAllocTerm(NXZone *zone, TermTag tag, int numSubterms, ...)
  418. {
  419.     Term *t;
  420.     int i;
  421.     va_list args;
  422.  
  423.     t = NXZoneCalloc(zone, sizeof(Term) + (numSubterms-1) * sizeof(Term *), 1);
  424.     t->tag = tag;
  425.     t->numSubterms = numSubterms;
  426.     va_start(args, numSubterms);
  427.     for (i = 0; i < numSubterms; i++)
  428.     t->subterms[i] = va_arg(args, Term *);
  429.     va_end(args);
  430.     return t;
  431. }
  432.  
  433. /*
  434.  * Frees a term and any associated data.  This routine can be used as the
  435.  * free function of a NXHashTable prototype, or as a proc passed to
  436.  * applyToTerms().
  437.  */
  438. void _EXPFreeTerm(const void *info, Term *data)
  439. {
  440.     Term *t = (Term *)data;
  441.  
  442.     if (t->tag == vectorTerm) {
  443.     free(t->data.vector.vals);
  444.     free(t->data.vector.name);
  445.     } else if (t->tag == varTerm)
  446.     free(t->data.var.name);
  447.     free(t);
  448. }
  449.  
  450. /*
  451.  * Makes sure a term is up to date.  Since terms recalculate any internal
  452.  * state lazily, this must be called before making use of a term's value.
  453.  * We apply this function recursively to all terms before evaluating an
  454.  * Expression, and apply to any term if we are asked to return the values
  455.  * held within the term (for example, from -varVector:vector:numVals:).
  456.  */
  457. static void updateTerm(void *data, Term *t)
  458. {
  459.     Expression *self = data;
  460.  
  461.     if (t->tag != vectorTerm)
  462.     return;        /* only vector terms require work to stay up to date */
  463.  
  464.   /* Ensure this term has the same resolution as the rest of the Expression. */ 
  465.     if (self->resolution != t->data.vector.resolution) {
  466.       /*
  467.        * We can change its resolution if we interpolate values for this term
  468.        * within a range.  Else if we were passed a list of values for this
  469.        * term, its an exception if the resolution is no longer in sync.
  470.        */
  471.     if (t->data.vector.hasRange) {
  472.         safeFree(&(void *)t->data.vector.vals);
  473.         t->data.vector.vals = NXZoneMalloc([self zone],
  474.                     self->resolution * sizeof(float));
  475.         t->data.vector.resolution = self->resolution;
  476.         t->data.vector.changed = YES;    /* remember to re-interpolate */
  477.     } else
  478.         NX_RAISE(expErrResolutionMismatch, self,
  479.                     (void *)t->data.vector.name);
  480.     }
  481.  
  482.     if (t->data.vector.changed) {
  483.     if (t->data.vector.hasRange) {
  484.       /* interpolate a list of values between min and max */
  485.         int i;
  486.         float delta;
  487.         float *val, *prevVal;
  488.  
  489.         i = self->resolution - 1;
  490.         if (i) {
  491.         delta = (t->data.vector.max - t->data.vector.min) / i;
  492.         prevVal = t->data.vector.vals;
  493.         *prevVal = t->data.vector.min;
  494.         val = prevVal + 1;
  495.         while (i--)
  496.             *val++ = *prevVal++ + delta;
  497.         *(val-1) = t->data.vector.max;    /* to be sure we hit max */
  498.         } else
  499.         *t->data.vector.vals = t->data.vector.min;
  500.     } else {
  501.       /* scan the list of values passed in to find the min and max */
  502.         int i;
  503.         float newMin, newMax;
  504.         float *val;
  505.  
  506.         val = t->data.vector.vals;
  507.         newMin = newMax = *val++;
  508.         for (i = t->data.vector.resolution; i--; val++) {
  509.         if (*val > newMax)
  510.             newMax = *val;
  511.         else if (*val < newMin)
  512.             newMin = *val;
  513.         }
  514.         t->data.vector.min = newMin;
  515.         t->data.vector.max = newMax;
  516.     }
  517.     t->data.vector.changed = NO;    /* we're now up to date */
  518.     }
  519. }
  520.  
  521. /*
  522.  * Ensures that the results calculated for this Expression are up to date.
  523.  * We first make sure all the terms in the parse tree are up to date by
  524.  * applying updateTerm() to all of them.  We then evaluate the Expression
  525.  * for every n times, depending on the resolution, storing all the results
  526.  * and caclulating their min and max. 
  527.  */
  528. - (void)_updateResults
  529. {
  530.     int i;
  531.     float *f;
  532.  
  533.     if (!resultsValid) {
  534.     if (parseTree) {
  535.         applyToTerms(self->parseTree, updateTerm, self, -1);
  536.         safeFree(&(void *)results);
  537.         results = NXZoneMalloc([self zone], sizeof(float) * resolution);
  538.         *results = evalTerm(parseTree, 0);
  539.         resultsMin = *results;
  540.         resultsMax = *results;
  541.         for (i = 1, f = results + 1; i < resolution; i++, f++) {
  542.           /*
  543.            * We pass the loop count down through the evaluation recursion
  544.            * so vector terms can know which element of their vectors they
  545.            * should use for this evaluation.
  546.            */
  547.         *f = evalTerm(parseTree, i);
  548.         if (*f > resultsMax)
  549.             resultsMax = *f;
  550.         else if (*f < resultsMin)
  551.             resultsMin = *f;
  552.         }
  553.     } else
  554.         NX_RAISE(expErrNoText, self, NULL);
  555.     resultsValid = YES;
  556.     }
  557. }
  558.  
  559. #define MAX_ARGS    50
  560.  
  561. /*
  562.  * Evaluates a particular term.  In order to evaluate itself, any term with
  563.  * subterms must recursively evaluate those first.
  564.  */
  565. static float evalTerm(Term *t, int element)
  566. {
  567.     float result = 0.0;        /* initted to quiet -Wall */
  568.     float base;
  569.     float argsBuffer[MAX_ARGS];
  570.     float *args;
  571.     int i;
  572.  
  573.     switch (t->tag) {
  574.     case constantTerm:
  575.         NX_ASSERT(t->numSubterms == 0, "Wrong #subterms in evalTerm");
  576.         result = t->data.constant.val;
  577.         break;
  578.     case varTerm:
  579.         NX_ASSERT(t->numSubterms == 0, "Wrong #subterms in evalTerm");
  580.         result = t->data.var.val;
  581.         break;
  582.     case vectorTerm:
  583.         NX_ASSERT(t->numSubterms == 0, "Wrong #subterms in evalTerm");
  584.         result = t->data.vector.vals[element];
  585.         break;
  586.     case binOpTerm:
  587.         NX_ASSERT(t->numSubterms == 2 ||
  588.             (t->data.binOp.op == '-' && t->numSubterms == 1),
  589.                     "Wrong #subterms in evalTerm");
  590.         switch (t->data.binOp.op) {
  591.         case '+':
  592.             result = evalTerm(t->subterms[0], element) +
  593.                 evalTerm(t->subterms[1], element);
  594.             break;
  595.         case '-':
  596.             if (t->numSubterms == 2)
  597.             result = evalTerm(t->subterms[0], element) -
  598.                     evalTerm(t->subterms[1], element);
  599.             else
  600.             result = - evalTerm(t->subterms[0], element);
  601.             break;
  602.         case '*':
  603.             result = evalTerm(t->subterms[0], element) *
  604.                 evalTerm(t->subterms[1], element);
  605.             break;
  606.         case '/':
  607.             result = evalTerm(t->subterms[0], element) /
  608.                 evalTerm(t->subterms[1], element);
  609.             break;
  610.         case '%':
  611.             result = (int)rint(evalTerm(t->subterms[0], element)) %
  612.                 (int)rint(evalTerm(t->subterms[1], element));
  613.             break;
  614.         case '^':
  615.           /* optimize for raising to an integral power */
  616.             if (t->subterms[1]->tag == constantTerm &&
  617.                 t->subterms[1]->data.constant.isInt &&
  618.                 t->subterms[1]->data.constant.val >= 1) {
  619.             result = base = evalTerm(t->subterms[0], element);
  620.             for (i = t->subterms[1]->data.constant.val; --i; )
  621.                 result *= base;
  622.             } else
  623.             result = pow(evalTerm(t->subterms[0], element),
  624.                     evalTerm(t->subterms[1], element));
  625.             break;
  626.         default:
  627.             NX_ASSERT(FALSE, "Unknown binary op type in evalTerm");
  628.         }
  629.         break;
  630.     case funcTerm:
  631.       /*
  632.        * For functions, we first ensure we have a large enough buffer
  633.        * for the values of all the arguments.  If there are few enough
  634.        * arguments, we use a buffer on the stack instead of thrashing
  635.        * the heap.  We then buffer up all the results of evaluating
  636.        * the arguments, and then pass this array of argument values
  637.        * to the proc that we use to evaluate this type of function.
  638.        */
  639.         if (t->numSubterms > MAX_ARGS)
  640.         args = NXZoneMalloc(NXDefaultMallocZone(),
  641.                     sizeof(float) * t->numSubterms);
  642.         else
  643.         args = argsBuffer;
  644.         for (i = 0; i < t->numSubterms; i++)
  645.         args[i] = evalTerm(t->subterms[i], element);
  646.         result = t->data.func.type->evalFunc(t->numSubterms, args);
  647.             if (t->numSubterms > MAX_ARGS)
  648.         NXZoneFree(NXDefaultMallocZone(), args);
  649.         break;
  650.     default:
  651.         NX_ASSERT(FALSE, "Invalid term type in evalTerm");
  652.     }
  653.     return result;
  654. }
  655.  
  656. /* Utility routine to look up a variable by name in the variable hashtable. */
  657. static Term *termOfVar(Expression *self, const char *varName)
  658. {
  659.     Term key;
  660.  
  661.     if (self->parseTree) {
  662.     key.tag = varTerm;
  663.     key.data.var.name = (char *)varName;
  664.     return NXHashGet(self->varTerms, &key);
  665.     } else
  666.     NX_RAISE(expErrNoText, self, NULL);
  667. }
  668.  
  669. /* adds a variable term to the Expressions hashtable of them */
  670. - (Term *)_addVarTerm:(const char *)name
  671. {
  672.     Term *newTerm;
  673.     Term *existingTerm;
  674.  
  675.     newTerm = _EXPAllocTerm([self zone], varTerm, 0);
  676.     newTerm->data.var.name = NXCopyStringBufferFromZone(name, [self zone]);
  677.     existingTerm = NXHashInsertIfAbsent(varTerms, newTerm);
  678.     NX_ASSERT(existingTerm == newTerm, "_addVarTerm: called with existing term");
  679.     return newTerm;
  680. }
  681.  
  682. /* frees some storage, NULL'ing out the pointer */
  683. static void safeFree(void **data)
  684. {
  685.     free(*data);
  686.     *data = NULL;
  687. }
  688.  
  689. /* free function used in the NXHashTable prototype for functions */
  690. static void FunctionFree(const void *info, void *data)
  691. {
  692.     free(((Function *)data)->name);
  693.     free(data);
  694. }
  695.  
  696. /*
  697.  * Adds a func term to a HashTable of them.  Returns any existing entry
  698.  * with the same name, else NULL.
  699.  */
  700. static Function *addFuncTerm(NXHashTable *table, const char *name, int min, int max, EXPTermEvalFunc *func)
  701. {
  702.     Function *newFunc;
  703.     Function *existingType;
  704.  
  705.     newFunc = NXZoneMalloc(NXZoneFromPtr(table), sizeof(Function));
  706.     newFunc->name = NXCopyStringBufferFromZone(name, NXZoneFromPtr(table));
  707.     newFunc->minArgs = min;
  708.     newFunc->maxArgs = max;
  709.     newFunc->evalFunc = func;
  710.     existingType = NXHashInsertIfAbsent(table, newFunc);
  711.     if (existingType != newFunc)
  712.     return existingType;
  713.     else
  714.     return NULL;
  715. }
  716.  
  717. /*
  718.  * Returns a global table of all built in functions.  This table is shared
  719.  * by expressions that dont have application functions added to them.
  720.  */
  721. static NXHashTable *getBuiltInFuncs(void)
  722. {
  723.     if (!BuiltInFuncTable)
  724.     BuiltInFuncTable = makeBuiltInFuncTable(NXDefaultMallocZone());
  725.     return BuiltInFuncTable;
  726. }
  727.  
  728. /* Returns a new hashtable of all built in functions. */
  729. static NXHashTable *makeBuiltInFuncTable(NXZone *zone)
  730. {
  731.     NXHashTable *table;
  732.     NXHashTablePrototype FuncTermProto;
  733.     const BuiltInFunc *bif;
  734.     int i;
  735.  
  736.     FuncTermProto = NXStrStructKeyPrototype;
  737.     FuncTermProto.free = FunctionFree;
  738.     table = NXCreateHashTableFromZone(FuncTermProto, NUM_BUILTIN_FUNCS,
  739.                                 NULL, zone);
  740.     for (i = NUM_BUILTIN_FUNCS, bif = FuncList; i--; bif++)
  741.     (void)addFuncTerm(table, bif->name, 1, 1, bif->func);
  742.     return table;
  743. }
  744.  
  745. /* Returns the name of a term. */
  746. static char *termName(const Term *t)
  747. {
  748.     switch (t->tag) {
  749.     case varTerm:
  750.         return t->data.var.name;
  751.     case vectorTerm:
  752.         return t->data.vector.name;
  753.     default:
  754.         NX_ASSERT(FALSE, "Bogus term type in VarTermHash");
  755.         return NULL;
  756.     }
  757. }
  758.  
  759. /* hashing function for variable terms.  Used in hashtable prototypes. */
  760. static unsigned    VarTermHash(const void *info, const void *data)
  761. {
  762.     return NXStrHash(info, termName(data));
  763. }
  764.  
  765. /* comparison function for variable terms.  Used in hashtable prototypes. */
  766. static int VarTermCompare(const void *info, const void *data1, const void *data2)
  767. {
  768.     return NXStrIsEqual(info, termName(data1), termName(data2));
  769. }
  770.  
  771. @end
  772.  
  773. /* These procs implement the built in functions */
  774.  
  775. static float sinStub(int numArgs, float *arg)    { return sin(*arg); }
  776. static float cosStub(int numArgs, float *arg)    { return cos(*arg); }
  777. static float tanStub(int numArgs, float *arg)    { return tan(*arg); }
  778. static float asinStub(int numArgs, float *arg)    { return asin(*arg); }
  779. static float acosStub(int numArgs, float *arg)    { return acos(*arg); }
  780. static float atanStub(int numArgs, float *arg)    { return atan(*arg); }
  781. static float expStub(int numArgs, float *arg)    { return exp(*arg); }
  782. static float logStub(int numArgs, float *arg)    { return log(*arg); }
  783. static float log10Stub(int numArgs, float *arg)    { return log10(*arg); }
  784. static float sqrtStub(int numArgs, float *arg)    { return sqrt(*arg); }
  785.